(*
Types ( ** )

A note on types. F# is a statically and strongly typed language.
This means that it does not allow us to erroneously mix different types together, for example an array instead of a list.
Being statically typed means that the F# compiler must be able to verify, when the source code is being processed before being run, that all types are correct, and in particular that all functions receive as input values of the same type that the functions expect.
There exist dynamically typed languages such as Lua and Python, which do not have this restriction. While code written in those languages may be more flexible, it may also contain subtle bugs that are not found until very late in the development cycle.
A good rule of thumb is that reusable, complex libraries are best written in a statically typed language, while smaller programs (that may even use those libraries) can easily be written in a dynamically typed language.

F# has types, but until now we have not yet seen a trace of them. This happens because F# also uses type inference.
Type inference allows the F# compiler to infer through a fairly complex algorithm the type of the various identifiers of the program, without explicit user annotations.
If we select or copy-and-paste all the code written above in F# interactive then we will see the types of all the identifiers used above.

The first two are simple floating point values, that is 64 bits long rational numbers:
val dt : float
val g : float

Then we find the simulation step function, which takes as input the pair of ball position and ball velocity and returns as output a pair of the same shape (but with different values).
In F# we define a pair with the "*" operator; for example, float * float is a pair of floating point numbers, while int * int is a pair of integers and int * string is a pair of an integer and a string.
Pairs may also be nested. For example, we could build a pair int * (float * string) of an integer and a pair of a floating point number and a string.

When defining the type of a function, we use the "->" operator, which separates the input of the function from its output. A function that takes as input an integer and returns another integer as output would have type int -> int.

val simulation_step : float * float -> float * float

Of course we may mix together functions and pairs freely. F# has no limitations (apart from the programmer's fantasy) in terms of what types it supports.
For example, we could define a function that takes as input an integer, and returns as output the pair of a floating point number and a function from integers to integers. Such a function would have type:

int -> float * (int -> int)

A possible body for this function could be:

let strange i = (float i),(fun x -> x * i)

Notice that when we wish to create a function without giving it a name we can use the syntax "fun x -> BODY".
All the functions we have seen above could have been defined with this syntax.
For example, we could have written:

let simulation_step = fun (y,v) ->
  let y',v' = (y + v * dt, v + g * dt)
  if y' < 0.0 then
    (0.0,-v' * 0.7)
  else
    (y',v')

and to the compiler this would have been exactly the same as the definition we have seen above.

A function that performs some imperative commands and does not compute a meaningful output value usually returns "unit". Unit (also known as "void" in C-like languages) is a type with only one value, ().

val print_scene : float * float -> unit

A function that takes no meaningful parameters takes as input a value of type unit.

val simulation : unit -> unit


We could also explicitly give our type definitions, for example when we have a function with a lot of arguments (types act as a good form of documentation) or if the type inference algorithm fails (it does not happen often, but it definitely does happen).

We annotate a let binding like this:
let (x:int) = 10

and we can annotate a function and its parameters in a variety of ways:

let f (x:int) : int = x + 10
let g ((x,y):int*int) : int = x * y
let h : int * int -> int = fun (x,y) -> x * y + 2

When annotating a function with its types, we can also specify some and omit others, like:

let f (x:int,y) = x * y + 100

the type inference algorithm will use the annotations we have provided, and this may help type inference understand the type of a particularly difficult function it could not understand before.
So should the type inference get stuck, we do not always need to provide all the type annotations of our program but only certain key ones as "hints".
*)
namespace Chapter1
  (*
  General discussion ( * )

  We will now explain in depth the various constructs we have seen in action in the sample above.
  We start by showing how "let" works, and how we can use it to define values, tuples and functions.
  We will also show how we can create functions that manipulate other functions, and even recursive functions that can invoke themselves.
  We will see how to write a conditional, that is an expression that can either take a value or another, depending on some dynamic condition.
  We will see some of the imperative capabilities of F#, in particular mutable values and references, and we will combine mutability with statements such as the for-loop.
  The last aspects we will explore are quite advanced. We will define a function that can be partially specialized, that is which can receive its parameters one at a time rather than all together. We will define the same function with a generic type, so that it can be used in many different ways and with parameters of different type.
  *)
  module Examples =

    open System

    (*
    Let-binding and functions ( * )
    
    In this paragraph we discuss how we can use the "let" keyword to give a name to values and functions. We will also see how we can define functions that invoke themselves, and even functions that return other functions as their result.
    *)

    (*
    let-binding is a simple, yet extremely powerful construct.
    *)
    (*
    We can use it to give a name to a value so that we do not have to rewrite the same value many times, for example:
    *)
    let pi = 3.141592654

    (*
    We can also use let to assign many values at once, even of different types:
    *)
    let a,b,c = 1, 20.0, "hello"

    (*
    We can perform any operations on the right-hand-side of the equals sign:
    *)
    let a' = 2 + a * 3

    (*
    let may also be used to rebind a name.
    A bound name always refers to the latest time it was bound.
    For example, we could easily write:
    *)
    let f() =
      let x = 10
      let x = "hello"
      x
    (*
    And the function f would return the "hello" string, and not 10.
    An exception to this would be if we defined a function that captured a previous value before rebinding it:
    *)
    let f'() =
      let x = 10
      let g() = printf "%d\n" x
      let x = "hello"
      do g()
      x
    (*
    When we invoke the f' function, then what happens?
    First of all, x is bound to the value 10.
    Then we define the g function which will print the current x, that is 10.
    Finally we rebind x, but not g, which still refers to the previous x, and then we return the rebound x after invoking g.
    Calling the function f' will print "10" and return "hello".

    The ability to define a function such as g which captures inside its body a local value is extremely powerful.
    For example, consider the case where we have two characters in an RPG, one with just a sword and another with both sword and shield.
    Suppose we wish to print the contents of these characters inventories in a general manner, that is not knowing which character we are talking about.
    Then we could define a function that prints each character's inventory:
    *)

    let character1() =
      let sword = "Vorpal Sword"
      let print() = printf "%s\n" sword
      sword,print

    let character2() =
      let sword = "Glamdring"
      let shield = "Wooden Shield"
      let print() = printf "%s %s\n" sword shield
      (sword,shield),print

    let print_character() =
      let _,print1 = character1()
      let _,print2 = character2()
      if Console.ReadLine() = "1" then
        print1()
      else
        print2()

    (*
    Notice that the print functions defined inside character1 and character2 use local values such as sword or shield.
    These local values are said to be "captured" inside the "closure" of the print functions.

    A relatively advanced use of functional programming for games would be to define a character as a set of function, one for each action the character must be able to perform.
    Creating a character would return the set of functions that define that character, such as:

    let mk_character() =
      let shoot() = ...
      let move() = ...
      let speak() = ...
      shoot,move,speak
    *)

    (*
    Functions are indeed a very important part of a functional language such as F#.

    [[NB: While the above sentence is true and perfectly valid, using a modern functional language without any advanced use of its functional capabilities is an absolutely great idea nonetheless.
    F# is succint, statically typed, uses type inference (which is really handy) and offers many different capabilities.
    It can be used by seasoned object-oriented programmers, functional programming wizards, but also beginners who peacefully ignore its advanced capabilities until they need it.]]
    *)

    (*
    F# allows the definition of functions. Functions are mathematical formulas or sequences of commands (often intermixed).
    The interesting bit about functions is that their internal computations depend on parameters, which are passed from outside the function by its "caller".

    Suppose we have two, almost identical, pieces of code:

    let x = 2
    Console.Write(x.ToString())
    let y = x * 3 + 1

    and

    let x = 4
    Console.Write(x.ToString())
    let y = x * 3 + 1

    then instead of duplicating the code in two different points we could write it just once inside a function and then simply call the function:

    let f x =
      Console.Write(x.ToString())
      x * 3 + 1

    let y = f 2

    and

    let y = f 4


    Functions are defined as follows:

    let FUNCTION-NAME PARAMS = BODY

    for example, we could define:
    *)

    let incr x = x + 1

    (*
    A function can also be considered a value. A value of type function is defined as:

    fun PARAMS -> BODY

    having values of type function is quite handy, and is a trend that is being adopted in many other languages such as C# (lambda expressions) and C++ (lambdas).

    We could define such a function and pass it a parameter right away:
    *)

    let res = (fun x -> x * 2 + 1) 10

    (*
    We could also pass a function to another function. For example, consider the following function definition which takes as input a function g and passes it the parameter 10:
    *)

    let f'' g = g 10

    (*
    We can invoke f'' by passing it a function parameter built with the syntax we have seen above:
    *)

    let res1 = f'' (fun x -> x * 2 + 1)

    (*
    We can also invoke f'' by passing it a function defined with let:
    *)

    let res2 = f'' incr

    (*
    We can define a function that may call itself (that is, a "recursive" function) with a special form of let binding, "let rec". We can write:
    *)

    let rec factorial n =
      if n = 0 then 1
      else n * factorial (n-1)

    (*
    Had we forgotten the "rec" keyword, then the F# compiler would have given us an error in the line "else n * factorial (n-1)".
    *)

    (*
    If-then-else and conditionals ( * )
    
    In this paragraph we discuss how we can perform branches in our code according to dynamic conditions. In particular, we will show how we can make our program check if a certain condition holds, and if it does perform some computations while if it does not perform some other computations.
    Branching is a crucial aspect of programming. Without branching, programs would behave linearly and predictably (not much more power than a pocket-calculator), while with branching our programs can make interesting decisions.
    There are various ways to branch: if-then-else and pattern-matching, and we will see both.

    *)

    (*
    A very powerful construct is the choice construct, or "if-then-else". We use it when we have two possible computations at some point in our pogram, but which one to perform depends on some condition.
    We write
      if cond then
        BRANCH1
      else
        BRANCH2
    to denote code that will run BRANCH1 if "cond" is a boolean value that evaluates to "true" and it will run BRANCH2 if "cond" evaluates to "false".

    Boolean values are primitive values that can only have two values: "true" and "false". We can assign a boolean value like this:
    *)

    let x,y = true,false

    (*
    Boolean values have type "bool", so the types of the identifiers bound by the let above are:
    val y : bool
    val x : bool
    *)

    (*
    We can manipulate boolean values with the usual set of boolean operators, which are and (&&), or (||) and not (not):
    *)

    let p = not x
    let q = x && y
    let r = x || y

    (*
    The simple if allows us to write expressions like:
    *)

    let i = if p then 10 else 20
    let j = if q || r then "hello" else "ciao"
    let k = if i < 10 then "thank you" else (if i < 20 then "grazie" else "merci")

    (*
    We can either use parentheses or indentation to define nested ifs; for example, the last conditional could have been written as:

    let k = if i < 10 then
              "thank you"
            else
              if i < 20 then
                "grazie"
              else
                "merci"

    Also, if we have many nested ifs we can use the "elif" keyword:

    let k = if i < 10 then
              "thank you"
            elif i < 20 then
              "grazie"
            else
              "merci"

    which produces code which is more aligned and more pleasant to read.

    An if expression has the same type of its branches. This way the above let bindings result in the following types and values:
    val i : int = 20
    val j : string = "hello"
    val k : string = "grazie"

    An important thing to remember when it comes to conditionals is that both branches of an if must have the same type.
    Writing an expression like:
    if i > 10 then "hello" else 20
    is not allowed, since the result would have both string and int as its type. There are constructs to deal with this kind of situation, and we will see them in a later chapter.
    *)

    (*
    An alternative to conditionals in F# is pattern matching. Consider the Fibonacci function:
    *)

    let rec fibonacci n =
      if n = 0 then 0
      elif n = 1 then 1
      else fibonacci (n-1) + fibonacci (n-2)

    (*
    A nice looking way of defining this function uses the "match n with" construct, which specifies a value (n) and a series of tests to perform against it.
    The first test to succeed (the expression that corresponds to value n) runs its associated code:
    *)
    let rec fibonacci' n =
      match n with
      | 0 -> 0
      | 1 -> 1
      | n -> fibonacci' (n-1) + fibonacci' (n-2)

    (*
    Notice that the last test uses a wildcard, that is any value of "n" will always match against the last case.

    For those who know a C-like language, it helps to think of pattern matching as a kind of "switch" statement, but we will see that pattern matching is quite a bit more powerful than the simple switch in a later chapter.

    A function that begins with the following lines:
    let f x =
      match x with
      ...

    can be abbreviated into:
    let f =
      function
      ...

    This way the Fibonacci function could be written as:
    *)
    let rec fibonacci'' =
      function
      | 0 -> 0
      | 1 -> 1
      | n -> fibonacci'' (n-1) + fibonacci'' (n-2)

    
    (*
    Variables and statements ( * )
    
    In this paragraph we discuss the imperative abilities of the F# language.
    F# supports all the common imperative construct such as variables, references, for-loops, while-loops, etc. In this section we see some examples of imperative statements in action.
    *)

    (*
    As we mentioned above, F# is an imperative language.
    An important consequence of being imperative is the ability to define variables, that is identifiers that stand for values that may change with time.
    F# supports two different constructs to define variables: local mutable cells and heap-allocated references. Local mutable cells are local, often stack-allocated while references are pointers to writable locations on the heap.
    The biggest difference is that a function may not capture a mutable cell.
    We define and assign variables as follows:
    *)

    let mutable v1 = 0
    let v2 = ref 0

    do v1 <- v1 + 10
    do v2 := !v2 + 10

    (*
    Notice that a mutable cell can be read as a normal value of the same type, and it is assigned with the left arrow "<-" operator.
    Indeed, v1 has type int and can be used wherever an integer is expected.
    References, on the other hand, have a special type.
    A reference to an integer has type "int ref" (or ref<int>), a reference to a string has type "string ref" (or ref<string>) and so on:


    val v1 : int
    val v2 : int ref

    A reference is read with the ( ! ) operator, by writing !r where r is a reference.
    Reference assignment is done with the ( := ) operator, and we usually write:

    r := v

    to assign value v to reference r.

    Notice that assignment of a mutable cell or a reference is an expression with type unit, and as such is preceded by the language keyword "do".
    We could write:
    *)

    if i < 10 then
      do v1 <- v1 + 10
    else
      ()

    (*
    which can be abbreviated into:
    *)
    if i < 10 then
      do v1 <- v1 + 10

    (*
    Variables can be used inside for-loops for a very imperative style of programming.
    For example, the factorial function could be written with a for-loop and a mutable variable as:
    *)

    let factorial' n =
      let mutable prod = 1
      for i = 1 to n do prod <- prod * i
      prod

    (*
    The for-loop construct declares an identifier which ranges between two values, included.
    If we write
    for i = x to y do BODY

    then body will be executed for each value of i ranging from x to y including x and y themselves.
    This may be a source of errors for imperative programmers used to writing:
    for(int i = x; i < y; i++) BODY

    since they may expect that the last iteration is not performed.
    *)

    (*
    Generic functions and partial specialization ( ** )

    Warning: this section contains advanced and complicated notions (as the ( ** ) mark suggests). For this reason it is not recommended to read this section right away, not before getting some more familiarity with the rest of the language.
    Unless you already have experience with functional languages, generic types (or C++ templates), a good idea may be to read the book, and then come back to this section!

    We now discuss an additional way of defining the parameters of functions, and we also detail why the type of references is defined as we have seen above.
    
    This section discusses how we can build functions that can be partially specialized. Instead of having type x -> y, these functions have types like x1 -> x2 -> ... -> y. A function with such type may receive its parameters one at a time, and not all at the same time. Passing only some parameters to such a function generates another function which takes as input (obviously) less parameters.
    We will also see how we can give a generic type to a function. Having a generic type means that our function can receive as input values of any type. Instead of defining the same function over and over for any possible type, we define it once for all possible types and reuse it many times.

    These two techniques, combined with records, give programmers an incredibly powerful toolset that allows them to create incredibly flexible and expressive programs.
    *)

    (*
    We have seen that references can have type ref<int>, ref<string>, or ref<'a> (read "ref of alpha") for any type 'a.
    F# types and functions can be defined generically, that is their types may use so called type variables or generic type parameters.
    For example, consider the following function:
    *)

    let quadratic_int (a,b,c,x) = a * x * x + b * x + c

    (*
    Type inference (correctly) infers that this function has type int * int * int * int -> int.
    The same function could be forced, through type annotations, to work on floating point numbers:
    *)

    let quadratic_float (a:float,b,c,x) = a * x * x + b * x + c

    (*
    We annotate just one parameter with type float and the compiler infers the function to have type float * float * float * float -> float

    What if we wanted to write the quadratic function just once and for all?
    We could use the ability of the F# language to take and return functions as regular parameters.
    In particular, we could pass to the quadratic function the functions sum and product appropriate for the type of a, b, c and x:
    *)

    let quadratic (sum,prod,a,b,c,x) =
      let x_square = prod(x,x)
      let t1 = prod(x_square,a)
      let t2 = prod(x,b)
      sum(sum(t1,t2),c)

    (*
    Here the type inference algorithm does not have any information about the actual type of a, b, c or x.
    F# reasons like this:
    - a, b, c and x have some types, which we call 'a, 'b, 'c, 'x; we do not know that these types are
    - sum and prod take as input all of these types, and so these types must be the same (say 'a)
    - sum and prod are two functions that take as input two 'a and return an 'a as output

    The type of quadratic is a bit long, and is the following generic type:
    val quadratic : ('a * 'a -> 'a) * ('a * 'a -> 'a) * 'a * 'a * 'a * 'a -> 'a

    'a is a "type variable", and may be instanced to any type.
    So we could pass to the quadratic function parameters of any type, provided we can also give the function an appropriate sum and product between these types.
    *)

    let y1 = quadratic ((fun (x,y) -> x+y), (fun (x,y) -> x*y), 10, 4, -2, 3)
    let y2 = quadratic ((fun (x,y) -> x+y), (fun (x,y) -> x*y), 10.0, 4.0, -2.0, 3.0)

    (*
    F# is being smart enough to understand that in the first instance above the sum and product are integer operations while in the second instance they are float.

    The above function is now quite powerful, but it certainly lacks in style, both in its original definition and when called.
    Let's make it prettier inside! We wish for the quadratic function to have a body that looks more closely to the initial, non generic definitions.
    For this reason we define inside the quadratic function two local sum and product operators that invoke the sum and prod functions.
    Indeed, we can use let-binding to redefine an operator.
    Also notice that the global definitions of + and * are intact, since the redefinition is only inside the body of the quadratic function.

    Another improvement we can do is to pass the parameters to the quadratic function separated by spaces rather than by commas.
    When we define a function as
    let f (x,y) = ...

    we are requiring callers of the function to supply all the parameters x and y at the same time.
    On the other hand, when we define a function as
    let f x y = ...

    (the function now has type int -> int -> 'a)

    then we are allowing the callers of f to supply x without (yet) supplying y. For example, we could write:
    let g = f 0

    and g would be a perfectly valid function of type int -> 'a (one parameter has disappeared from the type because its value is 0).
    We call g with the (quite intuitive) name of "partial specialization" of f.
    The new definition of the quadratic function is the following:
    *)

    let quadratic' sum prod a b c x =
      let ( + ) = sum
      let ( * ) = prod
      x * a * x + b * x + c

    let y3 = quadratic' ( + ) ( * ) 10 4 -2 3
    let y4 = quadratic' ( + ) ( * ) 10.0 4.0 -2.0 3.0

    (*
    Now we can define the quadratic function for integers and floats through partial specialization and without having to redefine it explicitly:
    *)
    let quadratic_int' : int -> int -> int -> int -> int = quadratic' ( + ) ( * )
    let quadratic_float' : float -> float -> float -> float -> float = quadratic' ( + ) ( * )

    (*
    We could even define a quadratic function in particular, by leaving the x parameter still unspecified:
    *)
    let my_quadratic_fun = quadratic_float' 10.0 4.0 -2.0

    (*
    The resulting function has type float -> float, and we can pass it the final parameter (the x) as many times as we want:
    *)
    let my_y0 = my_quadratic_fun 0.0
    let my_y1 = my_quadratic_fun 1.0
    let my_y2 = my_quadratic_fun 2.0
    let my_y3 = my_quadratic_fun 3.0
    let my_y4 = my_quadratic_fun 4.0

